package com.mdnote.practice.binary_tree;

import sun.reflect.generics.tree.Tree;

/**
 * @author Rhythm-2019
 * @date 2020/10/1
 * @description 从中序与后序遍历序列构造二叉树
 */
public class LeetCode106 {

    public static void main(String[] args) {
        LeetCode106 leetCode106 = new LeetCode106();
        TreeNode treeNode = leetCode106.buildTree(new int[]{9, 3, 15, 20, 7}, new int[]{9, 15, 7, 20, 3});
        System.out.println(treeNode);


    }
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder.length == 0 || postorder.length == 0) {
            return null;
        }
        return _build(0, inorder.length - 1, inorder, 0, postorder.length - 1, postorder);
    }

    private TreeNode _build(int inStart, int inEnd, int[] inorder, int postStart, int postEnd, int[] postorder) {
        // Terminator
        if (inStart > inEnd || postStart > postEnd) {
            return null;
        }
        // Process
        TreeNode root = new TreeNode(postorder[postEnd]);
        int inIndex = 0;
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == root.val) {
                inIndex = i;
                break;
            }
        }
        int rightSize = inEnd - inIndex;
        // Drill down
        root.left = _build(inStart, inIndex - 1, inorder,
                            postStart, postEnd  - 1 - rightSize, postorder);
        root.right = _build(inIndex + 1, inEnd, inorder,
                            postEnd - rightSize, postEnd - 1, postorder);
        return root;
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
}
